package com.sicheng.algorithm.recursive.dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/11/19 16:18
 */
public class 电话号码的字母组合 {
    private static final String[] letterMap = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz" // 9
    };

    private static final List<String> result = new ArrayList<>();

    private static final StringBuilder path = new StringBuilder();

    public static void main(String[] args) {

        System.out.println(dfs("23"));
    }

    public static List<String> dfs(String target) {
        if (target != null && target.length() > 0)
            dfs(target, 0);

        return result;
    }

    public static void dfs(String target, int startIndex) {

        if (path.length() == target.length()) {
            result.add(path.toString());
            return;
        }
        int index = target.charAt(startIndex) - '0';
        String letters = letterMap[index];
        for (int i = 0; i < letters.length(); i++) {
            path.append(letters.charAt(i));
            dfs(target, startIndex + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
